package singlelist;


import java.security.PublicKey;
import java.util.List;

//  Definition for singly-linked list.
  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

  class Solution8 {

      public ListNode detectCycle (ListNode head) {
          ListNode slowNode = head;
          ListNode fastNode = head;
          while (fastNode != null && fastNode.next != null) {
              slowNode = slowNode.next;
              fastNode = fastNode.next.next;
              if (slowNode == fastNode) {
                  {
                      slowNode = head;
                      while (slowNode != fastNode) {
                          slowNode = slowNode.next;
                          fastNode = fastNode.next;
                      }
                      return fastNode;
                  }
              }
          }
          return null;
      }

      public boolean hasCycle (ListNode head) {
          ListNode slowNode = head;
          ListNode fastNode = head;
          while (fastNode != null && fastNode.next != null) {
              slowNode = slowNode.next;
              fastNode = fastNode.next.next;
              if (slowNode == fastNode) {
                  return true;
              }
          }
          return false;
      }
  }

  class Solution7 {
      public ListNode getIntersectionNode (ListNode headA, ListNode headB) {
          if (headA == null || headB == null) {
              return null;
          }

          //计算长度
          ListNode tmpNode = headA;
          int lenA = 0;
          while (tmpNode != null) {
              tmpNode = tmpNode.next;
              lenA++;
          }
          tmpNode = headB;
          int lenB = 0;
          while (tmpNode != null) {
              tmpNode = tmpNode.next;
              lenB++;
          }

          //长的先走len个长度
          int len = lenA - lenB;
          if (len < 0) {
              len = lenB - lenA;
              while (len != 0) {
                  headB = headB.next;
                  len--;
              }
          } else {
              while (len != 0) {
                  headA = headA.next;
                  len--;
              }
          }

          //开始查找相同节点
          while (headA != null) {
              if (headA == headB) {
                  return headA;
              } else {
                  headA = headA.next;
                  headB = headB.next;
              }
          }
          return null;
      }
  }

  class Solution6 {
      public boolean chkPalindrome (ListNode A) {
          if (A == null) {
              return false;
          }
          ListNode slowNode = A;
          ListNode fastNode = A;

          //找到中间节点slowNode
          while (fastNode != null && fastNode.next != null) {
              slowNode = slowNode.next;
              fastNode = fastNode.next.next;
          }

          //反转链表
          ListNode curNode = slowNode.next;
          ListNode curNext = null;
          while (curNode != null) {
              curNext = curNode.next;    //注意此行代码的顺序 放在第一行和最后一行导致结果会不同 核心是搞明白谁应该先存储好 应该是下一个节点信息优先保存 所以应该写在第一行
              curNode.next = slowNode;
              slowNode = curNode;
              curNode = curNext;
          }

          //开始判断回文
          while (A != slowNode) {
              if (A.val != slowNode.val) {
                  return false;
              }
              if (A.next == slowNode) {    //偶数个的情况
                  return true;
              }
              A = A.next;
              slowNode = slowNode.next;
          }
          return true;
      }
  }

  class Solution5 {

      public ListNode partition2 (ListNode pHead, int x) {
            ListNode smallerStart = null;
            ListNode smallerEnd = null;
            ListNode biggerStart = null;
            ListNode biggerEnd = null;

            ListNode curNode = pHead;

            while (curNode != null) {
                if (curNode.val < x) {
                    if (smallerStart != null) {
                        smallerEnd.next = curNode;
                        smallerEnd = smallerEnd.next;
                    } else {
                        smallerStart = curNode;
                        smallerEnd = curNode;
                    }
                } else {
                    if (biggerStart != null) {
                        biggerEnd.next = curNode;
                        biggerEnd = biggerEnd.next;
                    } else {
                        biggerStart = curNode;
                        biggerEnd = curNode;
                    }
                }
                curNode = curNode.next;
            }

            if (smallerStart == null) {
                return biggerStart;
            } else {
                smallerEnd.next = biggerStart;
            }

            if (biggerEnd != null) {
                biggerEnd.next = null;
            }

            return smallerStart;
      }

      public ListNode partition1 (ListNode pHead, int x) {
          if (pHead == null) {
              return null;
          }

          //有了虚拟头之后head就不需要单独判断了
          ListNode virtualHead = new ListNode(-1, pHead);
          ListNode curNode = virtualHead;
          ListNode bigNode = null;
          ListNode nextNode = null;
          while (curNode.next != null) {
              if (curNode.next.val >= x) {
                  bigNode = curNode.next;
                  nextNode =bigNode;
                  while (nextNode.next != null) {
                      if (nextNode.next.val >= x) {
                          break;
                      } else {
                          nextNode = nextNode.next;
                      }
                  }
                  curNode.next = bigNode.next;
                  bigNode.next = nextNode.next;
                  nextNode.next = bigNode;
              }
              curNode = curNode.next;
          }

          return virtualHead.next;
      }
  }

  class Solution4 {
      public ListNode mergeTwoLists2 (ListNode list1, ListNode list2) {
          if (list1 == null && list2 == null)
              return null;

          ListNode newHead = new ListNode(-1);
          ListNode tmpNode = newHead;

          while (list1 != null && list2 != null) {
              if (list1.val <= list2.val) {
                  tmpNode.next = list1;
                  tmpNode = list1;
                  list1 = list1.next;
              } else {
                  tmpNode.next = list2;
                  tmpNode = list2;
                  list2 = list2.next;
              }
          }

          if (list1 == null) {
              tmpNode.next = list2;
          } else if (list2 == null) {
              tmpNode.next = list1;
          }

          return newHead.next;
      }

      public ListNode mergeTwoLists (ListNode list1, ListNode list2) {
          if (list1 == null && list2 == null) {
              return null;
          } else if (list1 == null && list2 != null) {
              return list2;
          } else if (list1 != null && list2 == null) {
              return list1;
          }

          ListNode newHead = new ListNode(-1);
          ListNode tmpNode = null;
          if (list1.val <= list2.val) {
              newHead.next = list1;
              tmpNode = list1;
          } else {
              newHead.next = list2;
              tmpNode = list2;
          }

          while (list1.next != null && list2.next != null) {
              if (list1.val <= list2.val) {
                  tmpNode.next = list1;
                  tmpNode = list1;
                  list1 = list1.next;
              } else {
                  tmpNode.next = list2;
                  tmpNode = list2;
                  list2 = list2.next;
              }
          }

          return newHead;
      }
  }

  class Solution3{
      public ListNode FindKthToTail2 (ListNode head, int k) {
          if (head == null || k <= 0) {
              return null;
          }
          ListNode slowNode = head;
          ListNode fastNode = head;
          k--;
          while (k != 0) {
              if (fastNode.next == null) {
                  break;
              } else {
                  fastNode = fastNode.next;
                  k--;
              }
          }
          while (fastNode.next != null) {
              slowNode = slowNode.next;
              fastNode = fastNode.next;
          }
          return slowNode;
      }

      public ListNode FindKthToTail (ListNode head, int k) {
          int c = 0;
          if (head != null) {
              c++;
          } else {
              return null;
          }
          ListNode tmpNode = head;
          while (tmpNode.next != null) {
              tmpNode = tmpNode.next;
              c++;
          }
          if (k > c) {
              return null;
          }
          c -= k;
          tmpNode = head;
          while (c != 0) {
              tmpNode = tmpNode.next;
              c--;
          }
          return tmpNode;
      }
  }
  class Solution2 {
      public ListNode middleNode2 (ListNode head) {
          if (head == null)
              return null;
          ListNode slowNode = head;
          ListNode fastNode = head;
          while (fastNode.next != null) {
              if (fastNode.next.next == null) {
                  slowNode = slowNode.next;
                  break;
              } else {
                  slowNode = slowNode.next;
                  fastNode = fastNode.next.next;
              }
          }
          return slowNode;
      }
      public ListNode middleNode (ListNode head) {
          int c = 0;
          ListNode countNode = head;
          if (countNode != null) {
              c++;
          }
          while(countNode.next != null) {
              c++;
              countNode = countNode.next;
          }
          countNode = head;
          c /= 2;
          while (c != 0) {
              countNode = countNode.next;
              c--;
          }
          return countNode;
      }
  }
class Solution1 {
    public ListNode reverseList(ListNode head) {

        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        }

        ListNode curNode = head.next;
        head.next = null;
        ListNode curNext = new ListNode();
        while(curNode.next != null) {
            curNext = curNode.next;
            curNode.next = head;
            head = curNode;
            curNode = curNext;
         }
        curNode.next = head;
        head = curNode;
        return head;
        /**
         * 和头插法不同的是
         * 这里不会不断提供新的节点给你
         * 所以需要你存储好所有的下一个节点
         */
//        ListNode curNode = head;
//        ListNode tmpNext = new ListNode();  //存储下一个节点
//        while (curNode.next != null) {
//            tmpNext = curNode.next;  //存储下一个
//            curNode.next.next = curNode;  //反转一个
//            curNode = tmpNext;
//        }
//        head.next = null;  //将原来头节点的next赋值null
//        head = curNode;  //更换新的头节点
//        return head;


        /**
         没有head和只有head一个成员的情况
         */
//        if (head == null) {
//            return null;
//        } else if (head.next == null) {
//            return head;
//        }
//
        /**
         多个成员的情况
         */
//        ListNode forNext = new ListNode();
//        ListNode preNode = head;
//        while(preNode.next != null) {
//            forNext = preNode.next;  // 存储要反转的节点的引用(address)
//            preNode.next.next = preNode;
//            preNode = forNext;
//        }
//        head = preNode;
//        return head;
    }
}

public class Solution {

    public static void merge (int[] nums1, int m, int[] nums2, int n) {
        int[] num = new int[m+n];
        int cur1 = 0;
        int cur2 = 0;
        int i = 0;
        while (cur1 < m && cur2 < n) {
            if (nums1[cur1] <= nums2[cur2]) {
                num[i] = nums1[cur1];
                cur1++;
                i++;
            } else {
                num[i] = nums2[cur2];
                cur2++;
                i++;
            }
        }

        if (cur1 == m) {
            while(cur2 != n) {
                num[i] = nums2[cur2];
                cur2++;
                i++;
            }
        } else {
            while (cur1 != m) {
                num[i] = nums1[cur1];
                cur1++;
                i++;
            }
        }
        nums1 = num;
    }

    public static int removeDuplicates2 (int[] nums) {
        int[] num = new int[nums.length];
        int i = 0;
        int j = 0;
        while (j != nums.length - 1) {
            if (nums[j] != num[i]) {
                num[i++] = nums[j];
            }
            j++;
        }
        return 0;
    }

    public static int removeDuplicates1 (int[] nums) {
        int i = 0;
        int len = nums.length;
        while (i < len) {
            for (int j = i+1; j < len - 1; j++) {
                if (nums[i] == nums[j]) {
                    for (int k = j; k < len - 1; k++) {
                        nums[k] = nums[k+1];
                    }
                    j--;
                    len--;
                }
            }
            i++;
        }
        return len;
    }

    public static int removeDuplicates (int[] nums) {
        if (nums.length <= 1) {
        return nums.length;
        }

        int i = 0;
        int j = nums.length;
        int k = 0;
        while (i < j - 1) {
            if (nums[i] == nums[i+1]) {
                k = i+1;
                while (k != j-1) {    //覆盖
                    nums[k] = nums[k+1];
                    k++;
                }
                j--;
            } else {
                i++;
            }
        }
        return j;
}
}

class Tss {
    public static void main(String[] args) {
        int[] nums = {1,1};

        for (int x = 0; x < Solution.removeDuplicates(nums); x++) {
            System.out.print(nums[x] + " ");
        }
    }

    public static void main2(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        Solution.merge(nums1,3,nums2,3);
        for (int x:
             nums1) {
            System.out.println(x);
        }
    }



    public static void main1(String[] args) {
        int[] nums = {0,0,1,1,1,2,2,3,3,4};
//        int[] nums = {1,1,2,2,3,3,4,5,6,7,7};
//        int[] nums = {1,1,2};
        System.out.println("len = " + nums.length);
        int len = Solution.removeDuplicates(nums);
        System.out.println("========");
        System.out.println("len = " + len);
        for (int i = 0; i < len;  i++) {
            System.out.print(nums[i] + " ");
        }
    }
}
